package com.algomypractice.sort.timecomplexityon2;

import com.annotation.service.SortTest;

/**
 * @author: ZhouBert
 * @date: 2019/6/18
 * @description: 归并排序 把 2路归并排序 看成是一颗二叉树（归并树），实际归并的过程是二叉树的后序遍历
 */
public class MergeSort {

	/**
	 * 归并排序的入口方法
	 */
	@SortTest
	public static void mergeSort(int[] arr) {
		mergeSort(arr, 0, arr.length - 1);
	}

	private static void mergeSort(int[] arr, int startIndex, int endIndex) {
		if (endIndex == startIndex) {
			return;
		}
		int mid = (startIndex + endIndex) / 2;
		mergeSort(arr, startIndex, mid);
		mergeSort(arr, mid + 1, endIndex);
		merge(arr, startIndex, mid, endIndex);
	}

	/**
	 * 排序的关键代码
	 *
	 * @param arr
	 * @param left  左边数组的开始索引
	 * @param mid   左边数组的最后索引
	 * @param right 右边数据的最后索引
	 */
	private static void merge(int[] arr, int left, int mid, int right) {
		///重新申请数组
		int[] leftArr = new int[mid - left + 1];
		int[] rightArr = new int[right - mid];

		///将部分数组数据填入新数组中(此时为何不用插入排序，我的想法是此时的数组已经是部分有序了，再用插入排序就浪费了)
		for (int i = left; i < mid + 1; i++) {
			leftArr[i - left] = arr[i];
		}
		for (int i = mid+1; i < right + 1; i++) {
			rightArr[i - mid-1] = arr[i];
		}

		///子序列索引 i-left j-right
		int i = 0, j = 0;
		int k = left;

		while (i < leftArr.length && j < rightArr.length) {
			if (leftArr[i] < rightArr[j]) {
				arr[k] = leftArr[i];
				i++;
				k++;
			} else {
				arr[k] = rightArr[j];
				j++;
				k++;
			}
		}

		if (i == leftArr.length) {
			///当左边序列排序完毕
			while (j < rightArr.length) {
				arr[k] = rightArr[j];
				k++;
				j++;
			}
		} else {
			///当左边序列排序完毕
			while (i < leftArr.length) {
				arr[k] = leftArr[i];
				k++;
				i++;
			}
		}

	}
}
